import java.util.HashSet;
import java.util.Set;

public class Solution1079 {
    public int numTilePossibilities(String tiles) {
        Set<String> stringSet=new HashSet<>();
        for (int i=1;i<=tiles.length();i++){
            int[] visit=new int[tiles.length()];
            dfs(new StringBuilder(),visit,tiles,0,i,stringSet);
        }
        return stringSet.size();
    }

    private void dfs(StringBuilder stringBuilder, int[] visit, String tiles, int k, int n, Set<String> stringSet) {
        if (k==n){
            stringSet.add(stringBuilder.toString());
            return;
        }
        for (int i=0;i<tiles.length();i++){
            if (visit[i]==0){
                visit[i]=1;
                stringBuilder.append(tiles.charAt(i));
                dfs(stringBuilder,visit,tiles,k+1,n,stringSet);
                visit[i]=0;
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1079().numTilePossibilities("AAABBC"));
    }
}
